//如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。 
//
// 给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。 
//
// 字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：0
//解释：s 已经是优质字符串。
// 
//
// 示例 2： 
//
// 
//输入：s = "aaabbbcc"
//输出：2
//解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
//另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。 
//
// 示例 3： 
//
// 
//输入：s = "ceabaacb"
//输出：2
//解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
//注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 105 
// s 仅含小写英文字母 
// 
// Related Topics 贪心 字符串 排序 
// 👍 31 👎 0

  
package com.zwy.leetcode.editor.cn;

import java.util.*;

/**
 * @author zwy 
 */
public class MinimumDeletionsToMakeCharacterFrequenciesUnique{
    public static void main(String[] args) {
        Solution solution = new MinimumDeletionsToMakeCharacterFrequenciesUnique().new Solution();
        String s="bbcebab";
        solution.minDeletions(s);
      }
     
/**
 *时间复杂度为:
 * @author zwy 
 */ 
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minDeletions(String s) {
        Map<Character,Integer> map=new HashMap<>();
        int res=0;
        Character c=' ';
        int now=0;
        for (int i = 0; i < s.length(); i++) {
            c=s.charAt(i);
            if(map.containsKey(c)){
                map.put(c,map.get(c)+1);
            }
            else {
                map.put(c,1);
            }
        }
        Set<Character> set = map.keySet();
        int size = map.size();
        int []arr=new int[size];
        int i=0;
        for (Character character : set) {
            arr[i]=map.get(character);
            i++;
        }
        Arrays.sort(arr);
        now=arr[arr.length-1];
        for (int j = arr.length-2; j >=0 ; j--) {
            if(arr[j]>=now){
               res+=arr[j]-now+1;
               now=now-1;
               if(now<=0){
                   now=1;
               }
            }
            else {
                now=arr[j];
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}